import java.util.HashMap;
import java.util.LinkedList;

public class ReversNumber {

    public static void main(String[] args) {

//        System.out.println(reverseNum(Integer.MAX_VALUE / 10 * 10));


//        System.out.println(isPalindromeNOStr(121));
//        System.out.println(romanToInt("iv"));
        String[] aaa = {"flower", "flow", "flight"};
//        String[] aaa = {"dog", "racecar", "car"};
//        System.out.println(longestCommonPrefix(aaa));

//        String test = "()";
//        System.out.println(isValid(test));

//        ListNode data = getData(10);
        ListNode listNode = mergeTwoLists(getData(2), getData(2));
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }


    }

    /**
     * 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
     * <p>
     * 示例：
     * <p>
     * 输入：1->2->4, 1->3->4
     * 输出：1->1->2->3->4->4
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        ListNode one = l1;
        ListNode two = l2;
        ListNode result = new ListNode(-1);
        ListNode head = result;
        while (one != null && two != null) {

            if (one.val > two.val) {
                result.next = two;
                result = two;
                two = two.next;
            } else {
                result.next = one;
                result = one;
                one = one.next;
            }
        }

        if (one != null) {
            result.next = one;
        }
        if (two != null) {
            result.next = two;
        }



        return head.next;
    }

    private static ListNode getData(int num) {
        ListNode pointer = new ListNode(-1);
        ListNode head = pointer;
        for (int i = 0; i < num; i++) {
            pointer.next = new ListNode(i);
            pointer = pointer.next;
        }

        return head.next;
    }


    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    /**
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
     * 有效字符串需满足：
     * <p>
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     *
     * @param s
     * @return
     */
    public static boolean isValid(String s) {
        LinkedList<String> sb = new LinkedList();

        HashMap<String, String> plantten = new HashMap<>();
        plantten.put(")", "(");
        plantten.put("]", "[");
        plantten.put("}", "{");


        for (int i = 0; i < s.length(); i++) {

            if (s.length() / 2 > sb.size()) {
                return false;
            }

            String item = String.valueOf(s.charAt(i));


            switch (item) {
                case "(":
                case "[":
                case "{":
                    sb.addLast(item);
                    break;
                case ")":
                case "]":
                case "}":
                    if (sb.size() == 0) {
                        return false;
                    }

                    String last = sb.getLast();
                    if (!last.equals(plantten.get(item))) {

                        return false;
                    }

                    sb.removeLast();
                    break;
                default:
                    break;

            }

        }
        return sb.size() == 0;


    }

    /**
     * 编写一个函数来查找字符串数组中的最长公共前缀。
     * <p>
     * 如果不存在公共前缀，返回空字符串 ""。
     *
     * @param strs
     * @return
     */
    public static String longestCommonPrefix(String[] strs) {

        if (strs == null || strs.length == 0) {
            return "";
        }
        if (strs.length == 1) {
            return strs[0];
        }

        String temp = strs[0];
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < temp.length(); i++) {
            char charTemp = temp.charAt(i);//d
            boolean isSame = true;
            //比较每个item的相对应位置的字符是否相等,只要有一个不相等,则退出总循环
            for (int j = 1; j < strs.length; j++) {
                String item = strs[j];//第j个字符串
                if (item.length() - 1 < i) {//iitem已经达到最大长度
                    isSame = false;
                } else {
                    char charAt = item.charAt(i);//r
                    if (charTemp - charAt != 0) {
                        isSame = false;
                        break;
                    }
                }
            }

            if (isSame) {
                sb.append(charTemp);
            } else {
                break;
            }

        }
        return sb.toString();
    }


    public static String[] keys = {"I", "V", "X", "L", "C", "D", "M", "IV", "IX", "XL", "XC", "CD", "CM"};
    public static int[] value = {1, 5, 10, 50, 100, 500, 1000, 4, 9, 40, 90, 400, 900};

    /**
     * 罗马数字转整数
     *
     * @param s
     * @return
     */
    public static long romanToInt(String s) {
        s = s.toUpperCase();
        HashMap<String, Integer> plant = new HashMap<>();
        for (int i = 0; i < keys.length; i++) {
            plant.put(keys[i], value[i]);
        }

        long sum = 0;
        for (int i = 0; i < s.length(); i++) {
            String key = "";
            if (i < s.length() - 1) {
                key = s.substring(i, i + 2);
                Integer num = plant.get(key);
                if (num != null) {
                    sum += num;
                    i++;
                    continue;
                }
            }
            key = s.substring(i, i + 1);
            sum += plant.get(key);
        }

        return sum;

    }


    public static boolean isPalindromeNOStr(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) {

            return false;
        }

        int revers = 0;
        while (x > revers) {
            revers = revers * 10 + x % 10;
            x /= 10;
        }

        return x == revers || x == revers / 10;


    }

    /**
     * 判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
     *
     * @param x
     * @return
     */
    public static boolean isPalindromeWithStr(int x) {

        if (x < 0) {
            return false;
        }

        String copy = String.valueOf(x);
        int length = copy.length();
        for (int i = 0; i < length / 2; i++) {
            if (copy.charAt(i) != copy.charAt(length - i - 1)) {
                return false;
            }
        }
        return true;

    }


    /**
     * 给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
     */
    public static int reverseNum(int x) {
        long result = 0;

        while (x != 0) {
            int temp = x % 10;
            result = result * 10 + temp;
            x /= 10;
        }
        if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE) {
            return 0;
        }
        return (int) result;


    }


}
